package special;

import java.util.*;

class DinnerPlates {
    int capacity = 0;
    int cursor = 0;
    List<Stack<Integer>> list;
    TreeSet<Integer> midSet = new TreeSet<>();

    public DinnerPlates(int capacity) {
        this.capacity = capacity;
        this.list = new ArrayList<>();
    }

    private int search(){
        int l = -1, r = list.size() - 1;
        while (++l < r){
            int m = (l + r) >>> 1;
            Stack<Integer> stack = list.get(m);
            if (!stack.isEmpty()){
                l = m;
            }else {
                r = m;
            }
        }
        if (list.get(l).size() == capacity){
            return -1;
        }else {
            return l;
        }
    }
    
    public void push(int val) {
        if (list.size() == 0){
            list.add(new Stack<>());
            list.get(0).push(val);
        }else {
            if (!midSet.isEmpty()){
                Integer index = midSet.first();
                list.get(index).add(val);
                if (index > cursor){
                    cursor = index;
                }
                if (list.get(index).size() == capacity){
                    midSet.pollFirst();
                }
            }else {
                int index = search();
                if (index == -1){
                    list.add(new Stack<>());
                    list.get(list.size() - 1).add(val);
                    cursor++;
                }else {
                    list.get(index).add(val);
                    if (index > cursor){
                        cursor = index;
                    }
                }
            }
        }
    }
    
    public int pop() {
        if (cursor < 0){
            return -1;
        }
        Stack<Integer> stack = list.get(cursor);
        if (!stack.isEmpty()){
            Integer ans = stack.pop();
            midSet.add(cursor);
            while (cursor >= 0 && list.get(cursor).isEmpty()){
                cursor--;
            }
            return ans;
        }
        return -1;
    }
    
    public int popAtStack(int index) {
        if (index >= list.size()){
            return -1;
        }else {
            Stack<Integer> mid = list.get(index);
            if (mid.isEmpty()){
                return -1;
            }else {
                Integer ans = mid.pop();
                while (cursor >= 0 && list.get(cursor).isEmpty()){
                    cursor--;
                }
                midSet.add(index);
                return ans;
            }
        }
    }
}